package com.leetcode.algorithm.y22.m05;

/**
 * 152. 乘积最大子数组
 * https://leetcode.cn/problems/maximum-product-subarray/description/
 * 
 * @author jie.deng
 *
 */
class Question0152Solution02 {

	public int maxProduct(int[] nums) {
		int len = nums.length;
		// DP状态定义：
		// -10 <= nums[i] <= 10,存在正负的情况
		// dp[i][0]表示以第 i 个元素结尾的乘积最大子数组的乘积
		// dp[i][1]表示以第 i 个元素结尾的乘积最小子数组的乘积
		int[][] dp = new int[len][2];
		// 初始化状态
		dp[0][0] = nums[0];
		dp[0][1] = nums[0];

		// 状态转移方程
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(nums[i], dp[i - 1][0] * nums[i]);
			dp[i][0] = Math.max(dp[i][0], dp[i - 1][1] * nums[i]);
			dp[i][1] = Math.min(nums[i], dp[i - 1][0] * nums[i]);
			dp[i][1] = Math.min(dp[i][1], dp[i - 1][1] * nums[i]);
		}

		// 乘积最大:max(dp[0...len-1][0])
		int maxProduct = dp[0][0];
		for (int i = 1; i < len; i++) {
			maxProduct = Math.max(maxProduct, dp[i][0]);
		}
		return maxProduct;
	}

}